package recursion

import problem.Problem

class Q21MergeTwoSortedLists extends Problem {

  def mergeTwoLists(l1: ListNode, l2: ListNode): ListNode = {
    if (l1 == null) l2
    else if (l2 == null) l1
    else {
      if (l1.x <= l2.x) {
        merge(l1, l1.next, l2)
        l1
      }
      else {
        merge(l2, l1, l2.next)
        l2
      }
    }
  }

  def merge(c: ListNode, l1: ListNode, l2: ListNode): Unit = {
    if (l1 == null) c.next = l2
    else if (l2 == null) c.next = l1
    else {
      if (l1.x <= l2.x) {
        c.next = l1
        merge(c.next, l1.next, l2)
      }
      else {
        c.next = l2
        merge(c.next, l1, l2.next)
      }
    }
  }

  override def test(): Unit = {
    val a = nodes(1, 2, 4)
    val b = nodes(1, 3, 4)
    println(mergeTwoLists(a, b))
  }
}
